/**
 * @Author 12629
 * @Date 2022/4/3 10:48
 * @Description：
 */
public class HashBuck {
    static class Node {
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    public Node[] array;

    public int usedSize;//存放的数据的个数

    public static final double DEFAULT_LOAD_FACTOR = 0.75;//默认的负载因子

    public HashBuck () {
        array  = new Node[8];
    }

    /**
     *
     * @param key
     * @param val
     * @return 代表你插入的元素的val
     */
    public boolean put(int key,int val) {

        Node node = new Node(key,val);
        //1、位置
        int index = key % array.length;

        //2、遍历这个下标的链表
        Node cur = array[index];//就是一个链表的头节点
        while (cur != null) {
            if(cur.key == key) {
                cur.val = val;//更新val值
                return false;
            }
            cur = cur.next;
        }
        //3、遍历完成了当前下标的链表，开始进行插入
        node.next = array[index];
        array[index] = node;
        this.usedSize++;
        //4、存放元素之后，判断当前哈希桶当中的负载因子 是否超过了默认的负载因子
        if(loadFactor() >= DEFAULT_LOAD_FACTOR) {
            //5、扩容
            resize();
        }
        return true;
    }

    /**
     * 扩容的同时 要进行重新哈希
     */
    private void resize() {
        //1、重新申请2倍的数组
        Node[] tmp = new Node[array.length*2];
        //2、遍历原来的数组，把每个下标的链表的节点，都重新进行哈希
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while (cur != null) {
                int newIndex = cur.key % tmp.length;//新的数组的下标
                Node curNext = cur.next;//先要记录下来下一个
                cur.next = tmp[newIndex];
                tmp[newIndex] = cur;
                cur = curNext;//这里注意
            }
        }
        array = tmp;
    }

    public int get(int key) {
        //1、确定位置
        int index = key % array.length;
        Node cur = array[index];
        while (cur != null) {
            if(cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }

    /**
     * 计算当前哈希桶当中的负载因子
     * @return
     */
    private double loadFactor() {
        return this.usedSize*1.0 / this.array.length;
    }

}
